package demo5;

import java.util.ArrayList;
import java.util.List;

//给你一个字符串 s，找到 s 中最长的回文子串。

public class Test {
    public static void main(String[] args) {

        System.out.println(longestPalindrome("bacabab"));

    }



    public static String longestPalindrome(String s) {
        //定义一个数组，用来保存符合回文字符串的开头（例如bab，把a的下标保存过来）
        List<Integer> list = new ArrayList<>();
        boolean flag = true;

        //保存目前的回文子串最大长度
        int max = 1;
        //保存当前最长的回文子串，默认先存字符串第一个
        String longestStr = s.charAt(0)+"";

        //扫描一遍字符串，看看有哪些符合(bab)的回文结构，就把中间点的下标保存进list中
        for (int i = 1; i < s.length()-1; i++) {
            if(s.charAt(i-1) == s.charAt(i+1)){
                //是回文结构，保存下标进list中
                list.add(i);
            }
        }
        //如果之前有bab的回文结构，需要更新回文子串
        if(list.size() != 0){
            max = 3;
            if(list.get(0)+1 == s.length()){
                longestStr = s.substring(list.get(0)-1);
            }else{
                longestStr = s.substring(list.get(0)-1,list.get(0)+2);
            }
            flag = false;
        }
        //将list中的每个符合条件的下标取出来，
        //判断以他们为起点向左右扩散的回文长度最大为多少
        for (int i = 0; i < list.size(); i++) {
            int length = 3;//保存当前回文串的长度，为3是因为中间字符也算
            int left = list.get(i)-2;//左边界
            int right = list.get(i)+2;//右边界
            //判断是否越界
            while(left >= 0 && right < s.length()){
                //判断是否依旧是回文结构
                if(s.charAt(left) == s.charAt(right)){
                    //是回文结构
                    //length+2，并判断是否比目前最长的长度要大
                    length = length+2;
                    if(length > max){
                        //找到更大的子串，就保存进可变字符串内
                        if(right == s.length()-1){
                            longestStr = s.substring(left);
                        }else{
                            longestStr = s.substring(left,right+1);
                        }
                        max = length;
                    }
                    //左右边界分别往外移动一位
                    left--;
                    right++;
                }else{
                    //不是回文结构，直接跳出循环
                    break;
                }
            }
        }

        //扫描完bab结构的回文节点，清空list，开始扫描aa结构的回文节点
        list.clear();
        //扫描一遍字符串，看看有哪些符合(aa)的回文结构，就把中间点的下标保存进list中
        for (int i = 0; i < s.length()-1; i++) {
            if(s.charAt(i) == s.charAt(i+1)){
                //是回文结构，保存下标进list中
                list.add(i);
            }
        }
        //如果之前没有bab的回文结构，此时最长的回文结构就是aa，需要更新回文子串
        if(list.size() != 0 && flag){
            max = 2;
            if(list.get(0)+1 == s.length()){
                longestStr = s.substring(list.get(0));
            }else{
                longestStr = s.substring(list.get(0),list.get(0)+2);
            }
        }
        //判断以他们为起点向左右扩散的回文长度最大为多少
        for (int i = 0; i < list.size(); i++) {
            int length = 2;//保存当前回文串的长度，为2是因为没有中间字符
            int left = list.get(i)-1;//左边界
            int right = list.get(i)+2;//右边界
            //判断是否越界
            while(left >= 0 && right < s.length()){
                //判断是否依旧是回文结构
                if(s.charAt(left) == s.charAt(right)){
                    //是回文结构
                    //length+2，并判断是否比目前最长的长度要大
                    length = length+2;
                    if(length > max){
                        //找到更大的子串，就保存进可变字符串内
                        if(right == s.length()-1){
                            longestStr = s.substring(left);
                        }else{
                            longestStr = s.substring(left,right+1);
                        }
                        max = length;
                    }
                    //左右边界分别往外移动一位
                    left--;
                    right++;
                }else{
                    //不是回文结构，直接跳出循环
                    break;
                }
            }
        }
        return longestStr;
    }
}
